There is a random number generation method in which n random bits are generated, a decimal representation value “a” corresponding to a binary representation value with the n random bits as values of its digits is compared to “p−1” in magnitude, the process is performed again if a>p−1 is satisfied, and, otherwise, “a” is adopted as a random number (see, for example, Non-patent literature 1). When “p” is a prime number, a random number on a prime field can be generated.